import java.util.ArrayList;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM21 旋转数组的最小数字
 * https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=295&tqId=23269&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
 * User: DELL
 * Data: 2022-11-02
 * Time: 17:53
 */


//二分法分情况讨论
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if (array[mid] > array[right]) {  //最小值在右边数组
                left = mid + 1;
            } else if (array[mid] < array[right]) {   //最小值在左边数组
                right = mid;   //此处切不可right = mid - 1，因为mid可能就是最小值
            } else {      //出现相等应让right--，不能让left++
                right--;
            }
        }
        //返回最小值
        return array[left];
    }
}

